package likou;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/08/17 00:04
 */
public class _438 {
    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc"));
    }

    public static List<Integer> findAnagrams(String s, String p) {
        int[] pnums = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pnums[p.charAt(i) - 'a']++;
        }
        List<Integer> res = new ArrayList<>();
        int left = 0;
        int right = 0;
        int[] snums = new int[26];
        char[] scs = s.toCharArray();
        while (left <= right && right < scs.length) {
            char c = scs[right];
            if (snums[c - 'a'] < pnums[c - 'a']) {
                snums[c - 'a']++;
                right++;
                if (right - left == p.length()) {
                    res.add(left);
                    snums[scs[left] - 'a']--;
                    left++;
                }
            } else {
                Arrays.fill(snums, 0);
                left++;
                while (left < scs.length && pnums[scs[left] - 'a'] == 0) {
                    left++;
                }
                if (left == scs.length) return res;
                right = left;
            }
        }
        return res;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> list = new ArrayList<>();
        boolean[] b = new boolean[26];
        int[] t = new int[26];
        int n = p.length();
        for (int i = 0; i < n; i++) {
            int c = p.charAt(i) - 'a';
            t[c]++;
            b[c] = true;
        }
        int[] m = new int[26];
        int left = 0, right = 0;
        while (right < s.length()) {
            int c = s.charAt(right) - 'a';
            if (!b[c]) {
                right++;
                left = right;
                m = new int[26];
                continue;
            }
            if (right - left + 1 < n) {
                m[c]++;
                right++;
                continue;
            }
            m[c]++;
            boolean bb = true;
            for (int j = 0; j < 26; j++) {
                if (m[j] != t[j]) {
                    bb = false;
                    break;
                }
            }
            if (bb) list.add(left);
            m[s.charAt(left) - 'a']--;
            left++;
            right++;
        }
        return list;
    }
}
